# Tri par sélection

## Introduction

Le tri par sélection est un tri simple qui consiste à chercher l'indice de
la plus petite valeur (ou la plus grande si tri décroissant) du tableau pour
la mettre au début. Exemple :

| indices | 0 | 1 | 2 | 3 | 4 | 5 |
| ------- | - | - | - | - | - | - |
| valeurs | 3 | 6 | 1 | 5 | 2 | 2 |

A la première itération, la plus petite valeur (1) est à l'indice 2. L'algorithme
intervertit alors cette valeur avec celle à l'indice 0 (3).

| indices | 0 | 1 | 2 | 3 | 4 | 5 |
| ------- | - | - | - | - | - | - |
| valeurs | 1 | 6 | 3 | 5 | 2 | 2 |

A la deuxième itération, on cherche l'indice de la plus petite valeur à partir
de l'indice 1. Cette fois c'est 2, à l'indice 4 (première occurence). L'algorithme
intervertit alors `tab[4]` avec `tab[1]`.

| indices | 0 | 1 | 2 | 3 | 4 | 5 |
| ------- | - | - | - | - | - | - |
| valeurs | 1 | 2 | 3 | 5 | 6 | 2 |

On remarque que la position avec laquelle la plus petite valeur est intervertie
est 0, puis 1… De même, on cherche la plus petite valeur à partir de 0, puis
1… Ainsi, la boucle principale est de la forme :

```python
for i in range(len(tab) - 1):
    k = indiceMin(tab, i) #à partir de i
    tmp = tab[k]
    tab[k] = tab[i]
    tab[i] = tmp
```

Lorsque il ne reste qu'une seule cellule, il est inutile de rechercher l'indice
de la plus petite valeur (…), d'où le `-1` dans `range`.


## Complexité

La complexité en temps de calcul de cet algorithme est en `O(n²)` ; il y a
précisément `(n - 1) x n / 2` opérations.

- `n - 1` est le nombre d'itérations (boucle principale).
- `n / 2`, est la moyenne du nombre d'itérations secondaires : `n - 1` lors
de la première itération principale, `1` à la dernière, soit `(n - 1 + 1) / 2`.


## Code de la fonction de tri

Dans cette version, indiceMini est intégré à la fonction :

```python
from typing import List

def triSelection(tab : List[float]) -> List[float]:
    """
    trie le tableau selon la méthode du tri par sélection, par ordre croissant
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triSelection([])
    []
    >>> triSelection([2, 1, 3])
    [1, 2, 3]
    >>> triSelection([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    
    global cout			#CPLX
    cout = 0			#CPLX
    for i in range(len(tab) - 1):
        #invariant: tab est trié jusqu'à l'indice i - 1, et tous les éléments à partir de i sont supérieurs à celui à l'indice i - 1
        
        #recherche de l'indice de la plus petite valeur :
        k = i
        for j in range(i + 1, len(tab)):
            cout += 1	#CPLX (dénombre le nombre de comparaisons)
            if tab[j] < tab[k]:
                k = j
                
        #permutation :
        if k != i: #permutation uniquement si nécessaire
            v = tab[i]
            tab[i] = tab[k]
            tab[k] = v
    return tab


if __name__ == "__main__":
    import doctest; doctest.testmod()
    t1 = [1,3,2,5,4]
    triSelection(t1)
    print(t1)
    n = len(t1)
    print("complexité théorique : " + str(int((n-1)*n/2)))
    print("complexité effective : " + str(cout))
```

Observer qu'en pratique, la complexité (effective) de l'algorithme est toujours
égale à la théorique. L'algorithme est stable.

*Remarque : il est inutile de renvoyer le tableau (car il est modifié par
la fonction — cf passage en entrée-sortie), mais c'est plus pratique pour
écrire des doctests.*